package leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author qingyan 2021-07-02
 */
public class Question119 {

    public static void main(String[] args) {
        Question119 question = new Question119();
        System.out.println(question.getRow(0));
    }


    public List<Integer> getRow(int numRows) {
        return dp(numRows);
    }

    /*
        方案一、动态规划
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][0]+dp[i-1][1]
        1
        1,1
        1,2,1
        1,

        ...
    */
    List<Integer> dp(int numRows) {
        int[] dp = new int[numRows + 1];
        dp[0] = 1;
        for (int i = 1; i <= numRows; i++) {
            int pre = dp[0];
            for (int j = 1; j <= i; j++) {
                int cur = dp[j];
                dp[j] = cur + pre;
                pre = cur;
            }
        }
        return Arrays.stream(dp).boxed().collect(Collectors.toList());
    }

}
